package com.gitee.wsl.struct.tree

import kotlin.jvm.JvmStatic


object TreeNodeManager {
    /**
     * Searches the tree node within the tree, which has the specified data,
     * starting from the current tree node and returns the first occurrence of it
     *
     * @param data data to find the tree node with
     * @return first occurrence of the searched tree node with data specified
     */
    fun <T:Any> find(baseNode: TreeNode, data: T?): TreeNode? {
        if (baseNode.isLeaf) {
            return if ((if (baseNode.data == null) data == null else baseNode.data == data)) baseNode as TreeNode else null
        }
        var searchedNode: TreeNode? = null
        traversePreOrder(baseNode, object : TraversalAction<TreeNode> {
            override fun perform(node: TreeNode) {
                if ((if (node.data == null) data == null else node.data == data)) {
                    searchedNode = node
                }
            }

            override val isCompleted: Boolean
                get() = searchedNode != null
        })
        return searchedNode as TreeNode?
    }

    /**
     * Searches the tree nodes within the tree, which have the specified data,
     * starting from the current tree node and returns the collection of the found
     * tree nodes
     *
     * @param data data to find the tree nodes with
     * @return collection of the searched tree nodes with data specified
     */
    fun <T> findAll(node: TreeNode, data: T?): List<TreeNode> {
        if (node.isLeaf) {
            return if ((if (node.data == null) data == null else node.data == data)) listOf(node) else emptyList()
        }
        val searchedNodes = ArrayList<TreeNode>()
        traversePreOrder(node, object : TraversalAction<TreeNode> {
            override fun perform(node: TreeNode) {
                if ((if (node.data == null) data == null else node.data == data)) {
                    searchedNodes.add(node)
                }
            }

            override val isCompleted: Boolean
                get() = false
        })
        return searchedNodes
    }

    /**
     * Traverses the tree in a pre ordered manner starting from the
     * current tree node and performs the traversal action on each
     * traversed tree node
     *
     * @param action action, which is to be performed on each tree
     * node, while traversing the tree
     */
    @JvmStatic
    fun traversePreOrder(node: TreeNode, action: TraversalAction<TreeNode>) {
        if (!action.isCompleted) {
            action.perform(node)
            if (!node.isLeaf) {
                (node as CategoryTreeNode).subtrees().forEach {subtree: TreeNode ->
                    traversePreOrder(subtree, action)
                }
            }
        }
    }

    /**
     * Traverses the tree in a post ordered manner starting from the
     * current tree node and performs the traversal action on each
     * traversed tree node
     *
     * @param action action, which is to be performed on each tree
     * node, while traversing the tree
     */
    fun traversePostOrder(node: TreeNode, action: TraversalAction<TreeNode>) {
        if (!action.isCompleted) {
            if (!node.isLeaf) {
                (node as CategoryTreeNode).subtrees().forEach{ subtree: TreeNode ->
                    traversePostOrder(subtree, action)
                }
            }
            action.perform(node)
        }
    }

    /**
     * Returns the pre ordered collection of nodes of the current tree
     * starting from the current tree node
     *
     * @return pre ordered collection of nodes of the current tree starting
     * from the current tree node
     */
    fun preOrdered(node: TreeNode): List<TreeNode> {
        if (node.isLeaf) {
            return listOf(node)
        }
        val mPreOrdered = ArrayList<TreeNode>()
        val action = populateAction<Any, TreeNode>(mPreOrdered)
        traversePreOrder(node, action)
        return mPreOrdered
    }

    /**
     * Returns the post ordered collection of nodes of the current tree
     * starting from the current tree node
     *
     * @return post ordered collection of nodes of the current tree starting
     * from the current tree node
     */
    fun postOrdered(node: TreeNode): List<TreeNode> {
        if (node.isLeaf) {
            return listOf(node)
        }
        val mPostOrdered = ArrayList<TreeNode>()
        val action = populateAction<Any, TreeNode>(mPostOrdered)
        traversePostOrder(node, action)
        return mPostOrdered
    }

    /**
     * Returns the collection of nodes, which connect the current node
     * with its descendants
     *
     * @param descendant the bottom child node for which the path is calculated
     * @return collection of nodes, which connect the current node with its descendants
     * @throws TreeNodeException exception that may be thrown in case if the
     * current node does not have such descendant or if the
     * specified tree node is root
     */
    fun path(node: TreeNode, descendant: TreeNode?): List<TreeNode?> {
        if (descendant == null || node.isLeaf || node == descendant) {
            return listOf(node)
        }
        val errorMessage = "Unable to build the path between tree nodes. "
        if (descendant.isRoot) {
            val message = errorMessage + "Current node $descendant is root"
            throw TreeNodeException(message)
        }
        val path: MutableList<TreeNode?> = mutableListOf()
        var _node = descendant
        path.add(_node)
        do {
            _node = _node!!.parent
            path.add(0, _node)
            if (node == _node) {
                return path
            }
        } while (!_node!!.isRoot)
        val message = errorMessage + "The specified tree node $descendant is not the descendant of tree node $node"

        throw TreeNodeException(message)
    }

    /**
     * Returns the common ancestor of the current node and the node specified
     *
     * @param node node, which the common ancestor is determined for,
     * along with the current node
     * @return common ancestor of the current node and the node specified
     * @throws TreeNodeException exception that may be thrown in case if the
     * specified tree node is null or the specified tree node
     * does not belong to the current tree or if any of the tree
     * nodes either the current one or the specified one is root
     */
    fun commonAncestor(
        baseNode: TreeNode,
        node: TreeNode
    ): TreeNode? {
        val errorMessage = "Unable to find the common ancestor between tree nodes. "

        if (!baseNode.root().contains(node)) {
            val message = errorMessage + "The specified tree node $node was not found in the current tree node $baseNode"
            throw TreeNodeException(message)
        }
        if (baseNode.isRoot
            || node.isRoot
        ) {
            val message =
                errorMessage + "The tree node ${if (baseNode.isRoot) baseNode else node} is root"
            throw TreeNodeException(message)
        }
        if (baseNode == node
            || isSiblingOf(baseNode, node)
        ) {
            return baseNode.parent
        }
        val thisNodeLevel = baseNode.level()
        val thatNodeLevel = node.level()
        return if (thisNodeLevel > thatNodeLevel) node.parent else baseNode.parent
    }

    /**
     * Checks whether the current tree node is a sibling of the specified node,
     * e.g. whether the current tree node and the specified one both have the
     * same parent
     *
     * @param node node, which sibling with the current tree node is to be checked
     * @return `true` if the current tree node is a sibling of the specified
     * node, e.g. whether the current tree node and the specified one both
     * have the same parent; `false` otherwise
     */
    fun isSiblingOf(baseNode:TreeNode, node: TreeNode?): Boolean {
        return (node != null && !baseNode.isRoot && !node.isRoot && baseNode.parent == node.parent)
    }

    /**
     * Checks whether the current tree node is the ancestor of the node specified
     *
     * @param node node, which is checked to be the descendant of the current tree
     * node
     * @return `true` if the current tree node is the ancestor of the node
     * specified; `false` otherwise
     */
    fun isAncestorOf(baseNode: TreeNode, node: TreeNode?): Boolean {
        if (node == null || baseNode.isLeaf
            || node.isRoot
            || baseNode == node
        ) {
            return false
        }
        var mNode = node
        do {
            mNode = mNode!!.parent
            if (baseNode == mNode) {
                return true
            }
        } while (!mNode!!.isRoot)
        return false
    }

    /**
     * Checks whether the current tree node is the descendant of the node specified
     *
     * @param node node, which is checked to be the ancestor of the current tree
     * node
     * @return `true` if the current tree node is the descendant of the node
     * specified; `false` otherwise
     */
    fun isDescendantOf(baseNode: TreeNode, node: TreeNode?): Boolean {
        if (node == null || baseNode.isRoot
            || node.isLeaf
            || baseNode == node
        ) {
            return false
        }
        var mNode: TreeNode? = baseNode
        do {
            mNode = mNode!!.parent
            if (node == mNode) {
                return true
            }
        } while (!mNode!!.isRoot)
        return false
    }

    /**
     * Populates the input collection with the tree nodes, while traversing the tree
     *
     * @param collection input collection to populate
     * @param <T></T>,K extends TreeNode> type of the tree node
     * @return traversal action, which populates the input collection with the tree nodes
     */
    fun <T, K : TreeNode> populateAction(collection: MutableList<TreeNode>): TraversalAction<K> {
        return object : TraversalAction<K> {
            override fun perform(node: K) {
                collection.add(node)
            }

            override val isCompleted: Boolean
                get() = false
        }
    }

    /**
     * Links the specified parent tree node reference as the parent to the
     * specified tree node
     *
     * @param node tree node to assign the parent tree node reference to
     * @param parent tree node to assign as a parent reference
     */
    @JvmStatic
    fun linkParent(node: TreeNode, parent: CategoryTreeNode?) {
       node.parent = parent
    }

    /**
     * Removes the parent tree node reference link from the specified tree node
     *
     * @param node tree node to remove the parent tree node reference assignment from
     */
    @JvmStatic
    fun unlinkParent(node: TreeNode) {
        node.parent = null
    }

    /**
     * Checks whether there is at least one not `null` element within
     * the input collection
     * <pre>
     * Validator.isAnyNotNull(Arrays.asList("foo", null))   = true
     * Validator.isAnyNotNull(null)                         = false
     * Validator.isAnyNotNull(Collections.emptyList())      = false
     * Validator.isAnyNotNull(Arrays.asList(null, null))    = false
    </pre> *
     *
     * @param collection input collection to check
     *
     * @return `true` if there is at least one not `null` element within
     * the input collection; `false` otherwise
     */
    fun isAnyNotNull(collection: List<Any?>): Boolean {
        if (collection.isEmpty()) {
            return false
        }
        for (item in collection) {
            if (item != null) {
                return true
            }
        }
        return false
    }

    /**
     * Checks whether the specified collection is @{code null}, empty or if
     * all of its elements are `null`
     * <pre>
     * areAllNulls(null)                          = true
     * areAllNulls(Collections.emptyList())       = true
     * areAllNulls(Arrays.asList(null, null))     = true
     * areAllNulls(Arrays.asList("foo", null))    = false
    </pre> *
     *
     * @param collection input collection to check
     *
     * @return `true` if the specified collection is `null`, empty
     * or if all of its elements are `null`; `false` otherwise
     */
    @JvmStatic
    fun areAllNulls(collection: List<Any?>): Boolean {
        return !isAnyNotNull(collection)
    }

    fun treeToMap(root: TreeNode, map: MutableMap<Any, Any>) {
        if (root is CategoryTreeNode) {
            root.subtrees().forEach{ node: TreeNode ->
                map[node.data as Any] = node
                if (!node.isLeaf) treeToMap(node, map)
            }
        } else {
            map[root.data as Any] = root
        }
    }
}